package com.pan.alg.niuke.stackque;

import java.util.PriorityQueue;

/**
 * 描述 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 *
 * <p>给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 * 要求：时间复杂度 O(nlogn)O(nlogn)，空间复杂度
 * O(1)O(1) 数据范围：0\le n \le 10000≤n≤1000， 1 \le K \le n1≤K≤n，数组中每个元素满足 0 \le val \le
 * 100000000≤val≤10000000
 */
public class FindKth {

    public int findKth(int[] a, int n, int K) {
        // write code here

        //小根堆
        PriorityQueue<Integer> sq = new PriorityQueue<>((o1, o2)->o1.compareTo(o2));

        for(int i=0;i<K;i++){
            sq.offer(a[i]);
        }

        for(int i=K;i<n;i++){
            int i1 = a[i];
            if(sq.peek().compareTo(i1)<0){
                sq.poll();
                sq.offer(i1);
            }
        }

        return sq.poll();
    }
}
